package com.cat.gridChart;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
*   @description https://leetcode.cn/problems/pacific-atlantic-water-flow/description/
*   @author 曲大人的喵
*   @create 2025/9/7 18:53
*   @since JDK17
*/

public class Solution11 {
    int n, m;
    boolean[][] res1, res2;
    int[][] h, d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    void dfs(int x, int y, boolean[][] res) {
        res[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + d[i][0], ny = y + d[i][1];
            if (nx == -1 || nx == n || ny == -1 || ny == m) {
                continue;
            }
            if (res[nx][ny] || h[x][y] > h[nx][ny]) {
                continue;
            }
            dfs(nx, ny, res);
        }
    }
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        h = heights;
        n = heights.length;
        m = heights[0].length;
        res1 = new boolean[n][m];
        res2 = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            dfs(i, 0, res1);
            dfs(i, m - 1, res2);
        }

        for (int i = 0; i < m; i++) {
            dfs(0, i, res1);
            dfs(n - 1, i, res2);
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (res1[i][j] && res2[i][j]) {
                    ans.add(new ArrayList<>(Arrays.asList(i, j)));
                }
            }
        }
        return ans;
    }
}
